There are n people whose IDs go from 0 to n - 1 and each person belongs exactly to one group. Given the array groupSizes of length n telling the group size each person belongs to, return the groups there are and the people's IDs each group includes.

You can return any solution in any order and the same applies for IDs. Also, it is guaranteed that there exists at least one solution.

Example 1:

Input: groupSizes = [3,3,3,3,3,1,3]
Output: [[5],[0,1,2],[3,4,6]]
Explanation: 
Other possible solutions are [[2,1,6],[5],[0,4,3]] and [[5],[0,6,2],[4,3,1]].

Example 2:

Input: groupSizes = [2,1,3,3,3,2]
Output: [[1],[0,5],[2,3,4]]

Constraints:

• groupSizes.length == n
• 1 <= n <= 500
• 1 <= groupSizes[i] <= n

解析

此題給予一數字陣列groupSize用來描述所求陣列中每個元素的分佈情形，即groupSize陣列中每個元素的值代表該元素屬於所求陣列中擁有該數量元素的子陣列，要求列出該所求陣列。難度為Medium。

可用Python的defaultdict依序將groupSize中有相同值的元素存到同一個dict。當該dict的元素個數與索引值相同時，代表該dict的值為一組符合所求的列表(list)，則將該dict的值存到結果列表res中，最後回傳res即為所求。

解法

時間複雜度：O(N)
空間複雜度：O(N)

from collections import defaultdict
class Solution:
    def groupThePeople(self, groupSizes: List[int]) -> List[List[int]]:
        sub_group, res = defaultdict(list), []
        for i, size in enumerate(groupSizes):
            # Append "i" to the value of the dict whose key is "size"
            sub_group[size].append(i)
            if len(sub_group[size]) == size:
                # Append the value(list) of the dict whose key is "size" to the result
                res.append(sub_group.pop(size))
        return res

備註

希望透過記錄解題的過程，可以對於資料結構及演算法等有更深一層的想法。
如有需訂正的地方歡迎告知，若有更好的解法也歡迎留言，謝謝。